package Sort;
/**
 * @author shy_black
 * @date 2019/3/8 15:48
 * @Description:
 */

/**
 * 1.找到要插入的位置
 * 2.将数据插入有序数组中
 * 将待排序的数据分为俩个区间，已排序区间与待排序区间，
 * ，算法刚开始时，已排序空间有一个元素，
 * 在待排序空间中选择第一个元素与已排序空间的最后一个空间比较，
 * 若比已排序的最大元素大，直接放入以排序空间最后一个位置，
 * 否则需要找到合适位置后进行插入
 */
public class 插入排序 {
    public static void insertSort(int[] arr) {
        long start = System.currentTimeMillis();

        if (arr.length <= 1)
            return;
        int i, j;
        for (i = 1; i < arr.length; i++) {
            int val = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > val; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = val;
        }
//        return arr;

        long end = System.currentTimeMillis();
        System.out.println("插入排序耗时" + (end - start) + "ms");
    }

}
